Hillenburg dilahirkan di kubu tentera Amerika Syarikat di Lawton, Oklahoma pada 21 Ogos 1961.[3][4] Bapanya ialah seorang pelukis dan pereka bagi syarikat aeroangkasa—termasuk McDonnell Douglas dan Rockwell Collins—dan telah menyumbang kepada Program Apollo.[5] Ibunya mengajar pelajar yang mempunyai masalah penglihatan.[3] Hillenburg berkata bahawa beliau mendapat kemahiran seni dari ibunya, dan memberitahu bahawa neneknya "sangat, sangat berbakat" dan "pelukis yang hebat".[5] Kakaknya mengikuti jejak langkah bapa mereka, dan menjadi pelukis serta pereka.[3] Bersama keluarganya, Hillenburg berpindah ke Orange County, California pada tahun 1962, ketika berusia setahun.[3][5] Beliau dibesarkan di Anaheim, California, di mana beliau menerima pendidikan menengah di Sekolah Tinggi Savanna.[5][6] Hillenburg ialah seorang yang aktif bersama kugirannya di sekolah menengah, bermain trompet.[5]

Kegilaan Hillenburg terhadap kehidupan marin telah berkembang sejak zaman kanak-kanak, ketika beliau menonton beberapa filem yang dihasilkan oleh ahli marin Perancis Jacques Cousteau.[3][5] Ketika beliau berada di perpustakaan pada tahun 1970-an, beliau melihat gambar hitam dan putih tentang menyelam.[5] Ketika berusia 15 tahun, beliau bersnorkel untuk kali pertama di Pantai Laguna;[5] pengalaman itu menggalakkan keputusannya untuk mengkaji kehidupan marin semasa kuliah.[3][6] Beberapa tahun selepas menamatkan pengajian dari Universiti Negeri Humboldt, beliau memperoleh ijazah sarjana muda dalam tafsiran dan perancangan sumber laut pada tahun 1984.[6][7] Semasa di Humboldt, beliau mendapat pelajaran seni tambahan, dan membuat Pameran di muzium.[5] Hillenburg berkata, "Saya berkembang menjadi seorang pelukis di Humboldt".[8]

Selepas mengenali seni, beliau menghadiri program induk dalam animasi eksperimen di Institut Seni California (CalArts) pada tahun 1992.[3][9] Hillenburg berkata, "Pada mulanya saya fikir bahawa jika saya pergi ke sekolah untuk seni, saya tidak akan mempunyai cara untuk mendapatkan nafkah, jadi saya fikir ia mungkin lebih bijak untuk mengekalkan semangat saya dan hobi seni serta mempelajari sesuatu yang lain. Sehingga akhir kerja sarjana saya, saya menyedari bahawa saya harus menyertai seni."[3] Beliau memberitahu pada tahun 1970-an, ketika beliau masih kecil, beliau dibawa ke pesta Pelancaran Animasi Antarabangsa di Los Angeles County Museum of Art, dan bertemu dengan juruanimasi Belanda Paul Driessen dengan karya kartunnya, The Killing An Egg.[10]